package basis.netease.hard;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 7-18 按位与为零的三元组
 * 给你一个整数数组 nums ，返回其中 按位与三元组 的数目。
 * 按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：
 * 0 <= i < nums.length
 * 0 <= j < nums.length
 * 0 <= k < nums.length
 * nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。
 * 提示：
 * 1 <= nums.length <= 1000
 * 0 <= nums[i] < 2^16
 * 注意：时间复杂度是 O(n^3)的算法，会超出时间限制。
 * 输入格式:
 * 整数数组nums，以",”分隔字符串形式作为输入
 * 输出格式:
 * 一个数字，字符串形式
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 2,1,3
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 12
 */
public class Main_14 {

    // 思路就是将1次O(n^3)拆成2次O(n^2)
    public static int countTriplets(int[] nums) {
        int[] cnt = new int[1 << 16];
        for (int x : nums) {
            for (int y : nums) {
                ++cnt[x & y];
            }
        }
        int ans = 0;
        for (int x : nums) {
            for (int mask = 0; mask < cnt.length; mask++) {
                if ((x & mask) == 0) {
                    ans += cnt[mask];
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = Arrays.stream(new Scanner(System.in).nextLine().split(","))
                .mapToInt(Integer::parseInt).toArray();
        System.out.println(countTriplets(nums));
    }

}
